﻿public class Solution {
    public bool CanPartition(int[] nums)
    {
        int sum = nums.Sum();
        if (sum % 2 != 0) return false;
        
        // 背包容量
        int N = sum / 2;
        int[] dp = new int[N + 1];
        for (int i = 0; i < nums.Length; i++)
        {
            for (int j = N; j >= nums[i]; j--)
            {
                dp[j] = Math.Max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        return dp[N] == N;
    }

    public static void Main(string[] args)
    {
        // 转换成01背包问题，看是否能把包装满
        int[] nums = [1, 5, 11, 5];
        Solution solution = new Solution();
        bool res = solution.CanPartition(nums);
        Console.WriteLine(res);
    }
}